Basic Paxos in Action

We learned the rules for the basic Paxos algorithm in the previous lesson. In this lesson, we will see those rules in action by running Paxos through three different scenarios. We will also see a situation where Paxos makes no progress. Lastly, we will present a solution to making progress and a complete Paxos protocol simulation involving all three roles: proposers, acceptors, and learners. This will also show the role of learners in knowing the current status of a slot's chosen value.

Previous value already chosen#

Let's see what happens when a value has already been chosen, and a new proposer comes in even with a higher proposal number. According to the rules, the new proposer is obligated to acknowledge the already chosen value and cannot enforce its own value.

Previous value not chosen, but new proposer sees it#

Due to network delays, messages can reach different servers at different times. The messages of different servers can intermingle. Even specific servers might take different times to process and act on a request due to variable load conditions. In the following example, server 5's proposal sees an older proposal value being accepted at server 3. As per the rules, server 5 acknowledges the value that has been accepted at server 3.

Previous value not chosen, new proposer doesn't see it#

It might be possible that the proposer at server 5 contacts a majority but does not yet see a proposal acceptance by server 1. In this case, server 5 will be able to get its own value chosen. It is important to note that later on, server 1's acceptor will need to change from the value mov to the chosen value jmp. This example highlights that an accepted value at an acceptor can change, but once a value is chosen, it should remain unchanged.

Liveness issues in the Paxos algorithm#

We will now discuss Paxos's liveness challenges in this section. We will also see the role of the learners in a full-fledged example where three participants are involved.

The dueling proposers#

The Paxos protocol says that an acceptor should always promise to a proposal if it has a proposal number higher than the one the acceptor has already promised. This condition can lead to a situation where the accept requests sent by the proposer are always being rejected by the acceptors (that promised to that proposer earlier). This happens because those acceptors receive prepare requests with greater proposal numbers before they receive the accept requests for the proposal they promised. And the acceptors have to promise to such proposals according to the protocol we have seen in the previous lesson.

If every time the acceptors receive a prepare request with a higher proposal number before receiving an accept request against a proposal that the acceptors promised earlier, none of the accept requests will be accepted (for example, server 3 in the following illustration is going through this situation). No progress is being made, and none of the proposers can pass step 2 of the protocol. Therefore, a value can never be chosen in this case. This dueling proposer situation is shown in the following illustration. Servers 1 and 5 are dueling to get their value accepted with no luck.

Let's see dueling proposers in action.

The distinguished proposer as a solution to dueling proposers#

To avoid the dueling proposers' situation, only a single proposer, called the distinguished proposer, is allowed to issue proposals. We can choose one of the proposers as a distinguished proposer so that all clients' requests have to funnel through it. A node with the highest ID can be elected as the current distinguished proposer. Nodes can share messages with each other to claim the leadership of being a distinguished proposer.

A leased-based scheme can be used where the current distinguished proposer reaffirms its position by sending messages to all nodes. If other nodes do not listen to such messages, they can initiate a fresh election algorithm. Even if there are two leaders at some point (for example, when some nodes were not able to hear from the leader due to network delays or partitioning), such a scenario does not pose a safety risk. A distinguished proposer helps make progress and eventually chooses a value. The protocol simulation with the distinguished proposer is shown in the following illustration:

Note: Having a distinguished proposer is an optimization and not a requirement. However, most Paxos implementations are based on the distinguished proposer.

The distinguished proposer is the only one who will try issuing proposals until it makes a value chosen. If the distinguished proposer fails before it reaches a consensus on a single value, then we need to elect another distinguished proposer.

We now know the workflow of the Paxos protocol. In the next lesson, we will revisit many of Paxos's rules to understand their rationale. While it may appear repetitive, this approach is intentional and aims to dispel the notion among practitioners that Paxos is challenging to grasp. By examining many examples, the core rules should become clearer. If you are short on time, you may skip the next lesson.